package codetop.microsoft.T93;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 18362
 * @Create: 2022-08-17 13:06:45 星期三
 */
class Solution {
    private List<String> result = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        dfs(s, new ArrayList<>(), 0);
        return result;
    }

    private int getValue(String s, int start, int end) {
        if (start == end)
            return s.charAt(start)-'0';
        int value = 0;
        for (int i=start; i<=end; ++i) {
            if (value == 0 && s.charAt(i) == '0')
                return -1;
            value = value * 10 + s.charAt(i) - '0';
        }
        return value;
    }

    private void dfs(String s, List<Integer> res, int cur) {
        if (cur == s.length()) {
            if (res.size() == 4) {
                StringBuilder sb = new StringBuilder();
                sb.append(res.get(0)).append('.').append(res.get(1)).append('.').append(res.get(2)).append('.').append(res.get(3));
                result.add(sb.toString());
            }
            return;
        }
        if (res.size() >= 4)
            return;
        for (int i=0; i<=2 && cur+i < s.length(); ++i) {
            int value = getValue(s, cur, cur+i);
            if (value >= 0 && value <= 255) {
                res.add(value);
                dfs(s, res, cur+i+1);
                res.remove(res.size()-1);
            }
        }
    }
}